#include <stdio.h>
#include <stdlib.h>
#include "红黑树.h"

#define rb_parent(r) ((r)->parent)
#define rb_is_red(r) ((r)->color==RED)
#define rb_is_black(r) ((r)->color==BLACK)
#define rb_set_black(r)  do { (r)->color = BLACK; } while (0)
#define rb_set_red(r)  do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c)  do { (r)->color = (c); } while (0)



//创建红黑树指针，指向根节点
PNode* create_rbtree()
{
	PNode*root = (PNode*)calloc(1, sizeof(PNode));
	return root;
}

//判断并插入结点，key是否存在，结点是否创建成功，
int insert_judge(PNode* root, int key)
{
	PNode node;

	if (search(*root, key) != NULL)
	{
		return -1;
	}

	if ((node = create_node(key, NULL, NULL, NULL)) == NULL)
	{
		return -1;
	}
	//插入
	insert_rb(root, node);
	return 0;
}

//树中是否存在key
PNode search(PNode x, int key)
{
	if (x == NULL || x->key == key)
		return x;
	if (key < x->key)
	{
		return search(x->left, key);
	}
	else
	{
		return search(x->right, key);
	}
}

//创建节点
PNode create_node(int key, PNode parent, PNode left, PNode right)
{
	PNode pnew = (PNode)calloc(1, sizeof(Node));
	pnew->key = key;
	pnew->parent = parent;
	pnew->left = left;
	pnew->right = right;
	pnew->color = RED;
	return pnew;
}

//插入结点，并调整树保持平衡
void insert_rb(PNode *root, PNode node)
{
	PNode father = NULL;
	PNode child = *root;
	while (child != NULL)
	{
		father = child;
		if (child->key < node->key)
		{
			child = child->right;
		}
		else
		{
			child = child->left;
		}
	}
	rb_parent(node) = father;
	if (father != NULL)
	{
		if (node->key < father->key)
		{
			father->left = node;
		}
		else
		{
			father->right = node;
		}
	}
	else
	{
		*root = node;
	}

	rb_insert_fixup(root, node);
}

//红黑树的调整
void rb_insert_fixup(PNode *root, PNode node)
{
	PNode parent, gparent;

	//插入的点肯定是叶子节点，若父节点为黑非空，则直接插入就好
	//父节点存在并且为红，分情况判断
	while ((parent = rb_parent(node)) && rb_is_red(parent))
	{
		gparent = rb_parent(parent);

		//若父节点是左孩子
		if (gparent->left == parent)
		{
			PNode uncle = gparent->right;
			//情形一，如果叔节点是红色
			if (uncle&&rb_is_red(uncle))
			{
				rb_set_black(parent);
				rb_set_black(uncle);
				rb_set_red(gparent);
				//此时根变为了红色，要继续判断
				node = gparent;
				continue;
			}

			//情形二，如果叔节点为黑，且当前是右孩子
			//叔为红色时到不了此处，所以不用判断
			//先左旋，再父子互换，变为了情形三
			if (parent->right == node)
			{
				PNode temp;
				rb_left_rotate(root, parent);
				temp = parent;
				parent = node;
				node = temp;
			}

			//情形三，叔节点为黑，当前节点是左孩子
			rb_set_black(parent);
			rb_set_red(gparent);
			rb_right_rotate(root, gparent);
		}
		//否则就是右孩子
		else
		{
			PNode uncle = gparent->left;
			//情形一，如果叔节点是红色
			if (uncle&&rb_is_red(uncle))
			{
				rb_set_black(parent);
				rb_set_black(uncle);
				rb_set_red(gparent);
				//此时根变为了红色，要继续判断
				node = gparent;
				continue;
			}

			//情形二，如果叔节点为黑，且当前是左孩子
			//叔为红色时到不了此处，所以不用判断
			//先左旋，再父子互换，变为了情形三
			if (parent->left == node)
			{
				PNode temp;
				rb_right_rotate(root, parent);
				temp = parent;
				parent = node;
				node = temp;
			}

			//情形三，叔节点为黑，当前节点是左孩子
			rb_set_black(parent);
			rb_set_red(gparent);
			rb_left_rotate(root, gparent);
		}
	}

	// 将根节点设为黑色
	rb_set_black(*root);
}

//左旋
void rb_left_rotate(PNode* root, PNode node)
{
	//节点左旋，必有右节点，但是可能没有左节点
	PNode rchild = node->right;
	node->right = rchild->left;
	if (rchild->left != NULL)
	{
		rchild->left->parent = node;
	}
	rchild->parent = rb_parent(node);
	if (node->parent == NULL)
	{
		*root = rchild;
	}
	else
	{
		if (node->parent->left == node)
		{
			node->parent->left = rchild;
		}
		else
		{
			node->parent->right = rchild;
		}
	}
	rchild->left = node;
	node->parent = rchild;
}

//右旋
void rb_right_rotate(PNode *root, PNode node)
{
	PNode lchild = node->left;
	node->left = lchild->right;
	if (lchild->right != NULL)
	{
		lchild->right->parent = node;
	}
	lchild->parent = node->parent;
	if (node->parent == NULL)
	{
		*root = lchild;
	}
	else
	{
		if (node->parent->left == node)
		{
			node->parent->left = lchild;
		}
		else
		{
			node->parent->right = lchild;
		}

	}
	lchild->right = node;
	node->parent = lchild;
}

//打印树前判断
void print_rbtree(PNode *root)
{
	if (root != NULL && (*root) != NULL)
		rbtree_print(*root, (*root)->key, 0);
}

//递归打印树
void rbtree_print(PNode node, int key, int direction)
{
	if (node != NULL)
	{
		if (direction == 0)    // tree是根节点
			printf("%2d(B) is root\n", node->key);
		else                // tree是分支节点
			printf("%2d(%s) is %2d's %6s child\n", node->key, rb_is_red(node) ? "R" : "B", key, direction == 1 ? "right" : "left");

		rbtree_print(node->left, node->key, -1);
		rbtree_print(node->right, node->key, 1);
	}
}

//先序
void pre_order(PNode node)
{
	if (node == NULL)
	{
		return;
	}
	printf("%3d", node->key);
	pre_order(node->left);
	pre_order(node->right);
}

//中序
void in_order(PNode node)
{
	if (node == NULL)
	{
		return;
	}
	in_order(node->left);
	printf("%3d", node->key);
	in_order(node->right);
}

//后序
void post_order(PNode node)
{
	if (node == NULL)
	{
		return;
	}
	post_order(node->left);
	post_order(node->right);
	printf("%3d", node->key);
}

int main()
{
	int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80,65,66,45,77,99,82,23,55,88,33,47 };
	//int a[] = { 12 ,1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17 };
	//得到数组长度
	int i, len = LENGTH(a);

	//指针指向根节点
	PNode* root = NULL;

	root = create_rbtree();
	printf("== 原始数据: ");
	for (i = 0; i < len; i++)
		printf("%d ", a[i]);
	printf("\n");

	for (i = 0; i < len; i++)
	{
		insert_judge(root, a[i]);
//插入时方便检查，可以关闭
#if CHECK_INSERT
		printf("== 添加节点: %d\n", a[i]);
		printf("== 树的详细信息: \n");
		print_rbtree(root);
		printf("\n");
#endif
	}
	//整体输出
	print_rbtree(root);
	//前序遍历
	printf("前序遍历是：\n");
	pre_order(*root);
	printf("\n");
	//中序遍历
	printf("中序遍历是：\n");
	in_order(*root);
	printf("\n");
	//后序遍历
	printf("后序遍历是：\n");
	post_order(*root);
	printf("\n");

	for (i = 0; i < len; i++)
	{
		printf("== 删除节点: %d\n", a[i]);
		delete_judge(root, a[i]);
		if (*root)
		{
			printf("== 树的详细信息: \n");
			print_rbtree(root);
			printf("\n");
		}
	}
	return 0;
}

//根据被删除结点所在位置，决定如何删除
void delete_judge(PNode* root, int key)
{
	PNode x, temp;
	if ((x = search(*root, key)) != NULL)
	{
		//左右孩子都有，选右孩子的最左边
		if (x->left != NULL && x->right != NULL)
		{
			temp = x;
			x = x->right;
			while (x->left != NULL)
			{
				x = x->left;
			}
			temp->key = x->key;
		}
		/*
			只有单个孩子的话，孩子结点必为红色
			不然不满足性质。
			所以孩子置黑，删除x，孩子作为新的x，删除完成return
		*/
		//只有左孩子
		else if (x->left != NULL)
		{
			temp = x->left;
			rb_set_black(temp);
			if (x== *root)
			{
				temp->parent = NULL;
				*root = temp;
				free(x);
			}
			else
			{
				temp->parent = x->parent;
				if (x == x->parent->left)
				{
					x->parent->left = temp;
				}
				else
				{
					x->parent->right = temp;
				}
				free(x);
			}
			return;
		}
		//只有右孩子
		else if (x->right != NULL)
		{
			temp = x->right;
			rb_set_black(temp);
			if (x == *root)
			{
				temp->parent = NULL;
				*root = temp;
				free(x);
			}
			else
			{
				temp->parent = x->parent;
				if (x == x->parent->left)
				{
					x->parent->left = temp;
				}
				else
				{
					x->parent->right = temp;
				}
				free(x);
			}
			return;
		}
		if (x == *root)
		{
			free(*root);
			*root = NULL;
			return;
		}
		rb_delete(root, x);
	}
}

//删除函数
void rb_delete(PNode* root, PNode x)
{
	PNode parent = x->parent;

	//后继为左孩子
	if (parent->left == x)
	{
		//case1:x为红
		if (rb_is_red(x))
		{
			parent->left = NULL;
			free(x);
		}
		//case2:x为黑
		else
		{
			//case 2-1:x的右孩子不为空
			if (x->right != NULL)
			{
				parent->left = x->right;
				rb_set_black(x->right);
				x->right->parent = x->parent;
				free(x);
			}
			//case 2-2:右孩子为空
			else
			{
				//删了
				parent->left = NULL;
				free(x);
				PNode bro = parent->right;
				//case 2-2-1:兄弟节点为红
				if (rb_is_red(bro))
					right_bro_red(root, bro, parent);
				//case 2-2-2:兄弟节点为黑
				else
					right_bro_black(root, bro, parent);
			}
		}
	}
	//为右孩子,则必没左孩子
	else
	{
		//case1:x为红
		if (rb_is_red(x))
		{
			parent->right = NULL;
			free(x);
		}
		//case2:x为黑
		else
		{
			//case 2-1:x的右孩子不为空
			if (x->right != NULL)
			{
				parent->right = x->right;
				rb_set_black(x->right);
				x->right->parent = x->parent;
				free(x);
			}
			//case 2-2:右孩子为空
			else
			{
				//删了
				parent->right = NULL;
				free(x);

				//case 2-2-1:兄弟节点为红
				PNode bro = parent->left;
				if (rb_is_red(bro))
					left_bro_red(root, bro, parent);
				
				//case 2-2-2:兄弟节点为黑
				else
					left_bro_black(root, bro, parent);
			}
		}
	}

}
/*
    删除后失衡需要和兄弟结点借时
    几种情况的处理函数
*/

//兄弟在左并且为红
void right_bro_red(PNode* root, PNode bro, PNode parent)
{
	bro = parent->right;
	if (rb_is_red(bro))
	{
		rb_left_rotate(root, parent);
		rb_set_black(bro);
		rb_set_red(parent);
		//还没完，还是少
		//但是变成兄弟节点为黑情形
	}
	right_bro_black(root, bro, parent);
}

//兄弟在右并且为黑
void right_bro_black(PNode* root, PNode bro, PNode parent)
{
	bro = parent->right;
	//兄弟节点左右孩子 SL、SR
	//case 2-2-2-1:SL为红，SR任意
	if (bro->left != NULL && rb_is_red(bro->left))
	{
		rb_right_rotate(root, bro);
		rb_left_rotate(root, parent);
		bro->parent->color = parent->color;
		rb_set_black(parent);

	}
	//case 2-2-2-2:SL为黑，SR为红
	else if (bro->right != NULL && rb_is_red(bro->right))
	{
		rb_left_rotate(root, parent);
		bro->color = parent->color;
		rb_set_black(parent);
		rb_set_black(bro->right);
	}
	else
	{
		// case 2-2-2-3:SL、SR全黑,parent为红
		if (rb_is_red(parent))
		{
			rb_set_black(parent);
			rb_set_red(bro);
		}
		//case 2-2-2-4:SL、SR全黑,parent为黑
		else
		{
			rb_set_red(bro);
			if (parent != (*root))
				left_bro_red(root, parent->parent->left, parent->parent);
			else
				return;
			//rb_delete(root, parent);
		}
	}
}

//上面两个的对称情况
void left_bro_red(PNode* root, PNode bro, PNode parent)
{
	bro = parent->left;
	if (rb_is_red(bro))
	{
		rb_right_rotate(root, parent);
		rb_set_black(bro);
		rb_set_red(parent);
		//还没完，还是少
		//但是变成兄弟节点为黑情形
	}
	left_bro_black(root, bro, parent);
}

void left_bro_black(PNode *root, PNode bro, PNode parent)
{
	//兄弟节点左右孩子 SL、SR
	//case 2-2-2-1:SR为红，SL任意
	bro = parent->left;
	if (bro->right != NULL && rb_is_red(bro->right))
	{
		rb_left_rotate(root, bro);
		rb_right_rotate(root, parent);
		bro->parent->color = parent->color;
		rb_set_black(parent);
	}
	//case 2-2-2-2:SR为黑，SL为红
	else if (bro->left != NULL && rb_is_red(bro->left))
	{
		rb_right_rotate(root, parent);
		bro->color = parent->color;
		rb_set_black(parent);
		rb_set_black(bro->left);
	}
	else
	{
		// case 2-2-2-3:SL、SR全黑,parent为红
		if (rb_is_red(parent))
		{
			rb_set_black(parent);
			rb_set_red(bro);
		}
		//case 2-2-2-4:SL、SR全黑,parent为黑
		else
		{
			rb_set_red(bro);
			if (parent != (*root))
				right_bro_red(root, bro, parent->parent);
			else
				return;
			//rb_delete(root, parent);
		}
	}
}